home *** CD-ROM | disk | FTP | other *** search
/ Aminet 30 / Aminet 30 (1999)(Schatztruhe)[!][Apr 1999].iso / Aminet / dev / lang / SmallEiffel.lha / SmallEiffel / sys / runtime / gc_lib.c < prev    next >
Encoding:
Text File  |  1998-12-22  |  13.9 KB  |  637 lines
  1. /*
  2. -- This file is  free  software, which  comes  along  with  SmallEiffel. This
  3. -- software  is  distributed  in the hope that it will be useful, but WITHOUT 
  4. -- ANY  WARRANTY;  without  even  the  implied warranty of MERCHANTABILITY or
  5. -- FITNESS  FOR A PARTICULAR PURPOSE. You can modify it as you want, provided
  6. -- this header is kept unaltered, and a notification of the changes is added.
  7. -- You  are  allowed  to  redistribute  it and sell it, alone or as a part of 
  8. -- another product.
  9. --          Copyright (C) 1994-98 LORIA - UHP - CRIN - INRIA - FRANCE
  10. --            Dominique COLNET and Suzanne COLLIN - colnet@loria.fr 
  11. --                       http://www.loria.fr/SmallEiffel
  12. --
  13. */
  14.  
  15. /* This file is automatically included when the Garbage Collector
  16.    is used (default, unless option -no_gc has been selected).
  17. */
  18.  
  19. void**stack_bottom;
  20. mch**gcmt=NULL;
  21. int gcmt_max=2048;
  22. int gcmt_used=0;
  23. fsoc*fsocfl=NULL;
  24. rsoc*rsocfl=NULL;
  25. int gc_is_off=1;
  26. unsigned int fsoc_count=0;
  27. unsigned int rsoc_count=0;
  28. void*gcmt_tail_addr=NULL;
  29.  
  30. void gc_sweep(void) {
  31.   mch** p2 = gcmt;
  32.   mch** p1 = gcmt+1;
  33.   mch**eogcmt=gcmt+gcmt_used;
  34.   if (FREE_CHUNK((*p2)->state_type)) {
  35.     if (RSO_FREE_CHUNK == ((*p2)->state_type)) {
  36.       ((rsoc*)(*p2))->next=NULL;
  37.       rsocfl=((rsoc*)(*p2));
  38.     }
  39.     else {
  40.       rsocfl=NULL;
  41.     }    
  42.   }
  43.   else {
  44.     ((*gcmt)->swfp)(*p2);
  45.     if (RSO_FREE_CHUNK==((*p2)->state_type)) {
  46.       ((rsoc*)(*p2))->next=NULL;
  47.       rsocfl=((rsoc*)(*p2));
  48.     }
  49.     else {
  50.       rsocfl=NULL;
  51.     }
  52.   }
  53.   while (p1 < eogcmt) {
  54.     if (FREE_CHUNK((*p1)->state_type)) {
  55.       if (RSO_FREE_CHUNK == ((*p1)->state_type)) {
  56.     if (RSO_FREE_CHUNK == ((*p2)->state_type)) {
  57.       if (((char*)(*p2))+(*p2)->size == ((char*)(*p1))) {
  58.         ((*p2)->size)+=((*p1)->size);
  59.         p1++;
  60.       }
  61.       else {
  62.         ((rsoc*)(*p1))->next=rsocfl;
  63.         rsocfl=((rsoc*)(*p1));
  64.         *(p2+1)=*p1; p2++; p1++;
  65.       }
  66.     }
  67.     else {
  68.       ((rsoc*)(*p1))->next=rsocfl;
  69.       rsocfl=((rsoc*)(*p1));
  70.       *(p2+1)=*p1; p2++; p1++;
  71.     }
  72.       }
  73.       else {
  74.     *(p2+1)=*p1; p2++; p1++;
  75.       }
  76.     }
  77.     else {
  78.       ((*p1)->swfp)(*p1);
  79.       if (RSO_FREE_CHUNK == ((*p1)->state_type)) {
  80.     if (RSO_FREE_CHUNK == ((*p2)->state_type)) {
  81.       if (((char*)(*p2))+(*p2)->size == ((char*)(*p1))) {
  82.         ((*p2)->size)+=((*p1)->size);
  83.         p1++;
  84.       }
  85.       else {
  86.         ((rsoc*)(*p1))->next=rsocfl;
  87.         rsocfl=((rsoc*)(*p1));
  88.         *(p2+1)=*p1; p2++; p1++;
  89.       }
  90.     }
  91.     else {
  92.       ((rsoc*)(*p1))->next=rsocfl;
  93.       rsocfl=((rsoc*)(*p1));
  94.       *(p2+1)=*p1; p2++; p1++;
  95.     }
  96.       }
  97.       else {
  98.     *(p2+1)=*p1; p2++; p1++;
  99.       }
  100.     }
  101.   }
  102.   gcmt_used=(p2-gcmt)+1;
  103. }
  104.  
  105. void gc_mark(void*p) {
  106.   if ((p>((void*)*gcmt))&&(p<=gcmt_tail_addr)) {
  107.     int i1=0;
  108.     int i2=gcmt_used-1;
  109.     int m=i2>>1;
  110.     mch*c;
  111.     for (;i2>i1;m=((i1+i2)>>1)) {
  112.       if (p<=((void*)gcmt[m+1])) {
  113.     i2=m;
  114.       }
  115.       else {
  116.     i1=m+1;
  117.       }
  118.     }
  119.     c=gcmt[i2];
  120.     if (!(FREE_CHUNK(c->state_type))) {
  121.       (c->amfp)(c,p);
  122.     }
  123.   }
  124. }
  125.  
  126. int gc_stack_size(void) {
  127.   void*stack_top[2]={NULL,NULL};
  128.   if (stack_top > stack_bottom) {
  129.     return ((void**)stack_top)-((void**)stack_bottom);
  130.   }
  131.   else {
  132.     return ((void**)stack_bottom)-((void**)stack_top);
  133.   }
  134. }
  135.  
  136. /*
  137.   To delay Garbage Collection when the stack is too large.
  138.   To allow fast increase of ceils.
  139. */
  140. #define FSOC_LIMIT (10240/((FSOC_SIZE)>>10))
  141. #define RSOC_LIMIT (10240/((RSOC_SIZE)>>10)) 
  142.  
  143. /*
  144.   When stack is too large, collection may be delayed.
  145. */
  146. #define GCLARGESTACK 50000
  147.  
  148. int garbage_delayed(void) {
  149.   if (gc_stack_size() > GCLARGESTACK) {
  150.     if (fsoc_count_ceil <= fsoc_count) {
  151.       if (rsoc_count_ceil <= rsoc_count) {
  152.     if ((fsoc_count<FSOC_LIMIT)&&(rsoc_count<RSOC_LIMIT)) {
  153.       fsoc_count_ceil++;
  154.       rsoc_count_ceil++;
  155.     return 1;
  156.     }
  157.     else return 0;
  158.       }
  159.       else {
  160.     if (fsoc_count<FSOC_LIMIT) {
  161.       fsoc_count_ceil++;
  162.       return 1;
  163.     }
  164.     else return 0;
  165.       }
  166.     }
  167.     else {
  168.       if (rsoc_count_ceil <= rsoc_count) {
  169.     if (rsoc_count<RSOC_LIMIT) {
  170.       rsoc_count_ceil++;
  171.       return 1;
  172.     }
  173.     else return 0;
  174.       }
  175.       else return 0;
  176.     }
  177.   }
  178.   else {
  179.     return 0;
  180.   }
  181. }
  182.  
  183. void gc_update_ceils(void) {
  184.   int c;
  185.  
  186.   /* Compute fsoc_count_ceil :
  187.    */
  188.   if (fsocfl==NULL) {
  189.     if (fsoc_count >= fsoc_count_ceil) {
  190.       if (fsoc_count_ceil<FSOC_LIMIT) {
  191.     fsoc_count_ceil<<=1;
  192.       }
  193.       else { 
  194.     c=fsoc_count+(fsoc_count/3);
  195.     if (fsoc_count_ceil < c)
  196.       fsoc_count_ceil=c;
  197.       }
  198.     }
  199.   }
  200.   else
  201.     if (fsoc_count_ceil < fsoc_count)
  202.       fsoc_count_ceil=fsoc_count;
  203.   /* Compute rsoc_count_ceil :
  204.    */
  205.   if (rsocfl==NULL) {
  206.     if (rsoc_count>=rsoc_count_ceil) {
  207.       if (rsoc_count_ceil<RSOC_LIMIT) {
  208.     rsoc_count_ceil<<=1;
  209.       }
  210.       else { 
  211.     c=rsoc_count+(rsoc_count/3);
  212.     if (rsoc_count_ceil < c)
  213.       rsoc_count_ceil=c;
  214.       }
  215.     }
  216.   }
  217.   else
  218.     if (rsoc_count_ceil < rsoc_count)
  219.       rsoc_count_ceil=rsoc_count;
  220. }
  221.  
  222. static void add_to_gcmt(mch*c) {
  223.   mch**p;
  224.   if (gcmt_used==gcmt_max) {
  225.     gcmt_max<<=1;
  226.     gcmt=realloc(gcmt,(gcmt_max+1)*sizeof(void*));
  227.   }
  228.   for(p=gcmt+(gcmt_used++ -1);(p>=gcmt)&&(*p>c);p--)
  229.     *(p+1)=*p;
  230.   *(p+1)=c;
  231. }
  232.  
  233. fsoc*new_fsoc(void) {
  234.   if(fsocfl!=NULL){
  235.     fsoc*r=fsocfl;
  236.     fsocfl=fsocfl->next;
  237.     return r;
  238.   }
  239.   else {
  240.     mch*r=malloc(FSOC_SIZE);
  241.     mch**p;
  242.     gc_update_ceils();
  243.     fsoc_count++;
  244.     if (gcmt_used==gcmt_max) {
  245.       gcmt_max<<=1;
  246.       gcmt=realloc(gcmt,(gcmt_max+1)*sizeof(void*));
  247.     }
  248.     for (p=gcmt+(gcmt_used++ -1);(p>=gcmt)&&(*p>r);p--)
  249.       *(p+1)=*p;
  250.     *(p+1)=r;
  251.     return (fsoc*)r;
  252.   }
  253. }
  254.  
  255. static char*rso_from_store(na_env*nae,int size) {
  256.   rsoh*r=(nae->store);
  257.   nae->store_left-=size;
  258.   if ((nae->store_left)>sizeof(rsoh)) {
  259.     r->header.size=size;
  260.     nae->store=((rsoh*)(((char*)(nae->store))+size));
  261.   }
  262.   else {
  263.     r->header.size=size+nae->store_left;
  264.     nae->store_left=0;
  265.   }
  266.   (r->header.magic_flag)=RSOH_UNMARKED;
  267.   ((void)memset((r+1),0,r->header.size-sizeof(rsoh)));
  268.   return (char*)(r+1);
  269. }
  270.  
  271. static void rsoc_sweep(rsoc*c) {
  272.   na_env*nae=c->nae;
  273.   rsoh*gp=(rsoh*)&(c->first_header);
  274.   rsoh*pp;
  275.   rsoh*eoc=((rsoh*)(((char*)c)+c->header.size));
  276.   c->free_list_of_large=NULL;
  277.   if (c->header.size > RSOC_SIZE) {
  278.     if (gp->header.magic_flag == RSOH_MARKED) {
  279.       gp->header.magic_flag=RSOH_UNMARKED;
  280.       c->next=nae->chunk_list;
  281.       nae->chunk_list=c;
  282.     }
  283.     else {
  284.       c->header.state_type=RSO_FREE_CHUNK;
  285.     }
  286.     return;
  287.   }
  288.   while (gp<eoc) {
  289.     while (gp->header.magic_flag == RSOH_MARKED) {
  290.       gp->header.magic_flag=RSOH_UNMARKED;
  291.       gp=((rsoh*)(((char*)gp)+gp->header.size));
  292.       if(gp>=eoc) {
  293.     c->next=nae->chunk_list;
  294.     nae->chunk_list=c;
  295.     return;
  296.       }
  297.     }
  298.     gp->header.magic_flag=RSOH_FREE;
  299.     pp=(rsoh*)(((char*)gp)+gp->header.size);
  300.     while ((pp<eoc)&&(pp->header.magic_flag != RSOH_MARKED)) {
  301.       pp->header.magic_flag=RSOH_FREE;
  302.       gp->header.size+=pp->header.size;
  303.       pp=((rsoh*)(((char*)pp)+pp->header.size));
  304.     }
  305.     if (gp->header.size >= RSOC_MIN_STORE) {
  306.       if (nae->store_left==0) {
  307.     nae->store_left=gp->header.size;
  308.     nae->store=gp;
  309.     nae->store_chunk=c;
  310.       }
  311.       else if (nae->store->header.size < gp->header.size) {
  312.     ((fll_rsoh*)nae->store)->next=nae->store_chunk->free_list_of_large;
  313.     nae->store_chunk->free_list_of_large=((fll_rsoh*)nae->store);
  314.     nae->store_left=gp->header.size;
  315.     nae->store=gp;
  316.     nae->store_chunk=c;
  317.       }
  318.       else {
  319.     ((fll_rsoh*)gp)->next=c->free_list_of_large;
  320.     c->free_list_of_large=((fll_rsoh*)gp);
  321.       }
  322.     }
  323.     gp=pp;
  324.   }
  325.   if (((rsoh*)(&c->first_header))->header.size >= 
  326.       (c->header.size-sizeof(rsoc)+sizeof(rsoh))){
  327.     c->header.state_type=RSO_FREE_CHUNK;
  328.     nae->store_chunk=NULL;
  329.     nae->store_left=0; 
  330.   }
  331.   else{
  332.     c->next=nae->chunk_list;
  333.     nae->chunk_list=c;
  334.   }
  335. }
  336.  
  337. static rsoc MRSOC = {{RSOC_SIZE,RSO_USED_CHUNK,
  338.               (void(*)(mch*,void*))gcna_align_mark,
  339.               (void(*)(mch*))rsoc_sweep},
  340.              NULL, NULL, NULL, {0,0}};
  341.  
  342. static void rsoc_malloc(na_env*nae){
  343.   rsoc*r=malloc(RSOC_SIZE);
  344.   rsoc_count++;
  345.   *r=MRSOC;
  346.   r->nae=nae;
  347.   nae->store=(&(r->first_header));
  348.   nae->store_left=RSOC_SIZE-sizeof(rsoc)+sizeof(rsoh);
  349.   nae->store_chunk=r;
  350.   r->next=nae->chunk_list;
  351.   nae->chunk_list=r;
  352.   add_to_gcmt((mch*)r);
  353. }
  354.  
  355. static rsoc*rsocfl_first_fit(int size) {
  356.   rsoc*pc=NULL;
  357.   rsoc*c=rsocfl;
  358.   while (c != NULL) {
  359.     if (c->header.size>=size) {
  360.       if (pc==NULL) {
  361.     rsocfl = c->next;
  362.       }
  363.       else {
  364.     pc->next=c->next;
  365.       }
  366.       return c;
  367.     }
  368.     pc=c;
  369.     c=c->next;
  370.   }
  371.   return NULL;
  372. }
  373.  
  374. static rsoc* rsocfl_best_fit(int size) {
  375.   int best_size;
  376.   rsoc *pc,*best_pc,*best_c, *c;
  377.   if (rsocfl==NULL)
  378.     return NULL;
  379.   pc=NULL;
  380.   best_pc=NULL;
  381.   best_c=NULL;
  382.   c=rsocfl;
  383.   while ((NULL!=c)&&(NULL==best_c)){
  384.     if (c->header.size>=size){
  385.       best_c=c;
  386.       best_pc=pc;
  387.       best_size=c->header.size;
  388.     }
  389.     pc=c;
  390.     c=c->next;
  391.   }
  392.   if (NULL==c){
  393.     if (best_pc != NULL)
  394.       best_pc->next=best_c->next;
  395.     else if (best_c==rsocfl)
  396.       rsocfl=best_c->next;
  397.     return best_c;
  398.   }
  399.   do{
  400.     if ((c->header.size>=size)&&(c->header.size<best_size)){    
  401.       best_c=c;
  402.       best_pc=pc;
  403.       best_size=c->header.size;
  404.     }
  405.     pc=c;
  406.     c=c->next;
  407.   } while(c!=NULL);
  408.   if (NULL==best_pc) {
  409.     rsocfl = best_c->next;
  410.   }
  411.   else {
  412.     best_pc->next=best_c->next;
  413.   }
  414.   return best_c;
  415. }
  416.  
  417. static int get_store_in(rsoc*c,int size) {
  418.   na_env*nae=c->nae;
  419.   fll_rsoh*pf=NULL;
  420.   fll_rsoh*f=c->free_list_of_large;
  421.   while (f != NULL) {
  422.     if (f->rsoh_field.size>=size) {
  423.       nae->store_left=f->rsoh_field.size;
  424.       nae->store=(rsoh*)f;
  425.       nae->store_chunk=c;
  426.       if (pf==NULL) {
  427.     c->free_list_of_large=f->next;
  428.       }
  429.       else {
  430.     pf->next=f->next;
  431.       }
  432.       return 1;
  433.     }
  434.     pf = f;
  435.     f = f->next;
  436.   }
  437.   return 0;
  438. }
  439.  
  440. char*new_na_from_chunk_list(na_env*nae,int size) {
  441.   rsoc*c=nae->chunk_list;
  442.   int csize;
  443.   while (c != NULL) {
  444.     if (get_store_in(c,size)) {
  445.       return rso_from_store(nae,size);
  446.     }    
  447.     c = c->next;
  448.   }
  449.   csize=size+(sizeof(rsoc)-sizeof(rsoh));
  450.   c=rsocfl_best_fit(csize);
  451.   if (c!=NULL){
  452.     if ((c->header.size > RSOC_SIZE)
  453.     &&
  454.     (c->header.size-csize > RSOC_MIN_STORE*4)) {
  455.       int csize_left=c->header.size-csize;
  456.       if ((csize_left%sizeof(double))!=0) {
  457.     csize_left-=(csize_left%sizeof(double));
  458.     csize=c->header.size-csize_left;
  459.       }
  460.       c->header.size=csize_left;
  461.       c->next=rsocfl;
  462.       rsocfl=c;
  463.       c=(rsoc*)(((char*)c)+csize_left);
  464.       add_to_gcmt((mch*)c);
  465.       c->header.amfp=(void(*)(mch*,void*))gcna_align_mark;
  466.       c->header.swfp=(void(*)(mch*))rsoc_sweep;
  467.     }
  468.     else {
  469.       csize=c->header.size;
  470.     }
  471.     c->header.size=csize;
  472.     c->header.state_type=RSO_USED_CHUNK;
  473.     c->free_list_of_large=NULL;
  474.     c->nae=nae;
  475.     nae->store=(&(c->first_header));
  476.     nae->store_left=csize-sizeof(rsoc)+sizeof(rsoh);
  477.     nae->store_chunk=c;
  478.     c->next=nae->chunk_list;
  479.     nae->chunk_list=c;
  480.     return rso_from_store(nae,size);
  481.   }
  482.   return NULL;
  483. }
  484.  
  485. char*new_na(na_env*nae,int size) { 
  486.   if (nae->store_left>0) {
  487.     nae->store->header.size=nae->store_left;
  488.     nae->store->header.magic_flag=RSOH_FREE;
  489.     if (nae->store_left >= RSOC_MIN_STORE) {
  490.       ((fll_rsoh*)(nae->store))->next=nae->store_chunk->free_list_of_large;
  491.       nae->store_chunk->free_list_of_large=((fll_rsoh*)nae->store);
  492.     }
  493.     nae->store_left=0;
  494.   }
  495.   if ((nae->store_chunk!=NULL)&&(get_store_in(nae->store_chunk,size))) {
  496.     return rso_from_store(nae,size);
  497.   }
  498.   {
  499.     char*r=new_na_from_chunk_list(nae,size);
  500.     if (r!=NULL)
  501.       return r;
  502.   }
  503.   if (rsoc_count<rsoc_count_ceil) {
  504.     if((size+sizeof(rsoc)-sizeof(rsoh))>RSOC_SIZE){
  505.       rsoc*c=malloc(size+sizeof(rsoc)-sizeof(rsoh));
  506.       rsoh*r=(&(c->first_header));
  507.       rsoc_count++;
  508.       *c=MRSOC;
  509.       c->header.size=size+sizeof(rsoc)-sizeof(rsoh);
  510.       c->nae=nae;
  511.       c->next=nae->chunk_list;
  512.       nae->chunk_list=c;
  513.       add_to_gcmt((mch*)c);
  514.       r->header.size=size;
  515.       (r->header.magic_flag)=RSOH_UNMARKED;
  516.       ((void)memset((r+1),0,size-sizeof(rsoh)));
  517.       return (char*)(r+1);
  518.     }
  519.     else {
  520.       rsoc_malloc(nae);
  521.       return rso_from_store(nae,size);
  522.     }
  523.   }
  524.   gc_start();
  525.   if (size<=(nae->store_left)) {
  526.     return rso_from_store(nae,size);
  527.   }
  528.   {
  529.     char*r=new_na_from_chunk_list(nae,size);
  530.     if (r!=NULL) {
  531.       return r;
  532.     }
  533.   }
  534.   if((size+sizeof(rsoc)-sizeof(rsoh))>RSOC_SIZE){
  535.     rsoc*c=malloc(size+sizeof(rsoc)-sizeof(rsoh));
  536.     rsoh*r=(&(c->first_header));
  537.     rsoc_count++;
  538.     *c=MRSOC;
  539.     c->header.size=size+sizeof(rsoc)-sizeof(rsoh);
  540.     c->nae=nae;
  541.     c->next=nae->chunk_list;
  542.     nae->chunk_list=c;
  543.     add_to_gcmt((mch*)c);
  544.     r->header.size=size;
  545.     (r->header.magic_flag)=RSOH_UNMARKED;
  546.     ((void)memset((r+1),0,size-sizeof(rsoh)));
  547.     gc_update_ceils();
  548.     return (char*)(r+1);
  549.   }
  550.   else {
  551.     rsoc_malloc(nae);
  552.     gc_update_ceils();
  553.     return rso_from_store(nae,size);
  554.   }
  555. }
  556.  
  557. void gcna_align_mark(rsoc*c,void*o) {
  558.   na_env* nae = c->nae;
  559.   fll_rsoh* f;
  560.   fll_rsoh* pf;
  561.   char* b = (char*)&(c->first_header);
  562.   if (((char*)o) > (((char*)c)+c->header.size)) {
  563.     return;
  564.   }
  565.   if (((((char*)o)-((char*)c))%sizeof(int)) != 0) {
  566.     return;
  567.   }
  568.   if ((((rsoh*)o)-1)->header.magic_flag!=RSOH_UNMARKED) {
  569.     return;
  570.   }
  571.   if (((char*)o)<((char*)(c+1))) {
  572.     return;
  573.   }
  574.   if (c->header.size > RSOC_SIZE) {
  575.     if (o == (c+1)) {
  576.       nae->gc_mark(o);
  577.     }
  578.     return;
  579.   }
  580.   pf=NULL;
  581.   f=c->free_list_of_large;
  582.   while ((f != NULL) && (f < ((fll_rsoh*)o))) {
  583.     pf=f;
  584.     f=f->next;
  585.   }
  586.   if (pf == NULL) {
  587.     pf=(fll_rsoh*)b;
  588.   }
  589.   while ((((rsoh*)pf)+1) < (rsoh*)o) {
  590.     pf = ((fll_rsoh*)(((char*)pf)+pf->rsoh_field.size));
  591.   }
  592.   {void* tmp = (((rsoh*)pf)+1);
  593.   if (o == tmp) {
  594.     nae->gc_mark(o);
  595.   } 
  596.   } 
  597. }
  598.  
  599. int rsocfl_count(void) {
  600.   int r=0;
  601.   rsoc*p=rsocfl;
  602.   while (p!=NULL) {
  603.     r++;
  604.     p=p->next;
  605.   }
  606.   return r;
  607. }
  608.  
  609. int fsocfl_count(void) {
  610.   int r=0;
  611.   fsoc*p=fsocfl;
  612.   while (p!=NULL) {
  613.     r++;
  614.     p=p->next;
  615.   }
  616.   return r;
  617. }
  618.  
  619. void rsocfl_info(void) {
  620.   int r=0;
  621.   int max=0;
  622.   rsoc*p=rsocfl;
  623.   printf(" rsocfl count = %d\n",rsocfl_count());
  624.   if (p!=NULL) {
  625.     printf(" rsocfl = [",r);
  626.     p=rsocfl;
  627.     while (p!=NULL) {
  628.       printf("%d",p->header.size);
  629.       if(max < p->header.size) max=p->header.size;
  630.       p=p->next;
  631.       if (p!=NULL)printf(",");
  632.     }
  633.     printf("]\n");
  634.     printf(" rsocfl max = %d\n",max);
  635.   }
  636. }
  637.